package com.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-11-16 11:03
 * @version: 1.0
 * @description: 爬楼梯问题
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * 输入：n = 3
 * 输出：3
 * 解释：有三种方法可以爬到楼顶。
 * 1. 1 阶 + 1 阶 + 1 阶
 * 2. 1 阶 + 2 阶
 * 3. 2 阶 + 1 阶
 * 条件：1 <= n <= 45
 **/
public class ClimbStairs {

    static Map<Integer,Integer> map = new HashMap<>();
    public static void main(String[] args) {
        System.out.println(climbStairs(4));
    }

    private static int climbStairs(int n) {
        if (n==1) return 1;
        if (n==2) return 2;
        if (map.containsKey(n)) return map.get(n);
        int sum = climbStairs(n - 1) + climbStairs(n - 2);
        map.put(n,sum);
        return sum;
    }

}
